package graph.weight;

import linear.Queue;

/**
 * 有权无向图
 */
public class EdgeWeightedGraph {
    private int V;
    private int E;
    private Queue<Edge>[] adj;

    public EdgeWeightedGraph(int V) {
        this.V = V;
        E = 0;
        adj = new Queue[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new Queue<>();
        }
    }


    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);

        adj[v].enqueue(e);
        adj[w].enqueue(e);

        E++;
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public Queue<Edge> adj(int v) {
        return adj[v];
    }

    //获取加权无向图的所有边
    public Queue<Edge> edges() {
        // 创建一个队列，存储所有的边
        Queue<Edge> allEdge = new Queue<>();
        // 遍历顶点，拿到每个顶点的邻接表
        for (int v = 0; v < this.V; v++) {
            // 遍历邻接表，拿到邻接表中的每条边
            for (Edge e : adj(v)) {
                /*
                因为无向图中，每条边对象Edge都会在两个顶点的邻接表中各出现一次，为了不重复获取，暂定
                一条规则：
                除了当前顶点v，再获取边e中的另外一个顶点w，如果v<w则添加，这样可以保证同一条边
                只会被统计一次
                */
                if (e.other(v) < v) {
                    allEdge.enqueue(e);
                }
            }
        }
        return allEdge;
    }

}
